589. A-функция от строчки

Дана строка S, состоящая из n символов. Определим функцию A(i) от первых i символов этой сроки следующим образом: A(i) равно такому максимально возможному k, что равны следующие строки:

S[1] + S[2] + S[3] + … + S[k],

S[i] + S[i – 1] + S[i – 2] + … + S[i – k + 1],

где S[i] – i-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом.

Напишите программу, которая вычислит значения функции A для заданной строчки для всех возможных значений i от 1 до n.

Вход. В первой строке записано одно число n (1 ≤ n ≤ 200000). Во второй строке записана строка длиной n символов, состоящая только из больших и (или) маленьких латинских букв.

Выход. Выведите n чисел – значения функции A(1), A(2), … A(n).

Пример входа	Пример выхода
5 aabaa	1 2 0 1 5

РЕШЕНИЕ

строки – z-функция

Анализ алгоритма

Совершим конкатенацию входной строки с ее обращенной (перевернутой). Пусть длина входной строки равна len. Тогда длина полученной строки равна 2* len. Вычислим z-функцию полученной строки. Остается вывести значения Z[2*len – 1], Z[2*len – 2], …, Z[len].

Пример

После конкатенации входной строки длины len = 5 с ее же обращенной, получим aabaaaabaa. Z-функция строки имеет вид (0, 1, 0, 2, 2, 5, 1, 0, 2, 1). Следовательно ответом будет последовательность Z[9], Z[8], …, Z[5] или 1, 2, 0, 1, 5.

Реализация алгоритма

Объявим рабочие строки.

string s, ss;

Функция z вычисляет и возвращает z-функцию.

vector<int> z(string &s)

{

int n = s.size();

vector<int> z(n, 0);

for (int i = 1, l = 0, r = 0; i < n; i++)

{

if (i <= r) z[i] = min(r - i + 1, z[i - l]);

while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;

if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;

}

return z;

}

Основная часть программы. Читаем входную строку s. Копируем строку s в ss. Обращаем ss. Совершаем конкатенацию входной строки с ее обращенной.

cin >> n;

cin >> s;

ss = s;

reverse(ss.begin(), ss.end());

s = s + ss;

Вычисляем z-функцию построенной строки.

vector<int> res = z(s);

Выводим ответ – значения Z[2*len – 1], Z[2*len – 2], …, Z[len], где len – длина входной строки s. Размер массива res в два раза больше длины входной строки s.

for (i = res.size() - 1; i >= s.size() / 2; i--)

cout << res[i] << " ";

cout << endl;